/*
 * Copyright (c) 2009-2010 HIT Microelectronic Center
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 *
 * Authors: Gou Pengfei
 *          Jin Yinghan
 *
 * Date: Dec. 2009
 *
 */

#ifndef __CPU_EDGE_EXE_HH__
#define __CPU_EDGE_EXE_HH__

#include <queue>
#include <map>
#include <set>

#include "base/statistics.hh"
#include "base/timebuf.hh"
#include "config/full_system.hh"
#include "cpu/edge/comm.hh"
#include "cpu/edge/lsq.hh"

class DerivEdgeCPUParams;
class FUPool;

template<class Impl>
class SimpleEdgeExecute
{
  public: 
    //Typedefs from Impl
    typedef typename Impl::CPUPol CPUPol;
    typedef typename Impl::DynInstPtr DynInstPtr;
    typedef typename Impl::EdgeBlockPtr EdgeBlockPtr;
    typedef typename Impl::EdgeBlock EdgeBlock;
    typedef typename Impl::CPU CPU;

    typedef typename CPUPol::IQ IQ;
    typedef typename CPUPol::LSQ LSQ;

    typedef typename CPUPol::TimeStruct TimeStruct;
    typedef typename CPUPol::Map2Execute Map2Execute;
    typedef typename CPUPol::Execute2Commit Execute2Commit;
    typedef typename CPUPol::Issue2Execute Issue2Execute;

    typedef TheISA::BlockID BlockID;
    typedef typename std::map<BlockID, EdgeBlockPtr>::iterator ExeBlockIt;

    friend class Impl::CPU;
    friend class CPUPol::IQ;

  public:
    /** Overall Execute stage status. Used to determine if the CPU can
     * deschedule itself due to a lack of activity.
     */
    enum Status {
        Active,
        Inactive
    };

    /** Status for Issue, Execute, and Writeback stages. */
    enum StageStatus {
        Running,
        Blocked,
        Idle,
        StartSquash,
        Squashing,
        Unblocking
    };

  private:
    /** Overall stage status. */
    Status _status;
    /** Dispatch status. */
    StageStatus dispatchStatus[Impl::MaxThreads];
    /** Execute status. */
    StageStatus exeStatus;
    /** Writeback status. */
    StageStatus wbStatus;

  public:
    /** Constructs a SimpleEdgeExecute with the given parameters. */
    SimpleEdgeExecute(CPU *_cpu, DerivEdgeCPUParams *params);

    /** Returns the name of the SimpleEdgeExecute stage. */
    std::string name() const;

    /** Registers statistics. */
    void regStats();

    /** Initializes stage; sends back the number of free IQ and LSQ entries. */
    void initStage();

    /** Returns the dcache port. */
    Port *getDcachePort() { return ldstQueue.getDcachePort(); }

    /** Sets main time buffer used for backwards communication. */
    void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);

    /** Sets time buffer to pass on instructions to commit. */
    void setExecuteQueue(TimeBuffer<Execute2Commit> *iq_ptr);

    /** Sets time buffer to receive instructions from map. */
    void setMapQueue(TimeBuffer<Map2Execute> * iq_ptr);

    /** Sets pointer to list of active threads. */
    void setActiveThreads(std::list<ThreadID> *at_ptr);

    /** Drains Execute stage. */
    bool drain();

    /** Resumes execution after a drain. */
    void resume();

    /** Completes switch out of Execute stage. */
    void switchOut();

    /** Takes over from another CPU's thread. */
    void takeOverFrom();

    /** Returns if Execute is switched out. */
    bool isSwitchedOut() { return switchedOut; }

    /** Squashes instructions in Execute for a specific thread. */
    void squash(ThreadID tid);

    /** Wakes all dependents of a completed instruction. */
    void wakeDependents(DynInstPtr &inst);

    /** Complete a memory reference inst in IQ. */
    void completeMemInst(DynInstPtr &inst);

    /** Tells memory dependence unit that a memory instruction needs to be
     * rescheduled. It will re-execute once replayMemInst() is called.
     */
    void rescheduleMemInst(DynInstPtr &inst);

    /** Re-executes all rescheduled memory instructions. */
    void replayMemInst(ThreadID tid);

    /** Sends an instruction to commit through the time buffer. */
    //void instToCommit(DynInstPtr &inst);
    void instBlockToCommit(EdgeBlockPtr &block);

    /** Inserts unused instructions of a thread into the skid buffer. */
    void skidInsert(ThreadID tid);

    /** Returns the max of the number of entries in all of the skid buffers. */
    int skidCount();

    /** Returns if all of the skid buffers are empty. */
    bool skidsEmpty();

    /** Updates overall Execute status based on all of the stages' statuses. */
    void updateStatus();

    /** Resets entries of the IQ and the LSQ. */
    void resetEntries();

    /** Tells the CPU to wakeup if it has descheduled itself due to no
     * activity. Used mainly by the LdWritebackEvent.
     */
    void wakeCPU();

    /** Reports to the CPU that there is activity this cycle. */
    void activityThisCycle();

    /** Tells CPU that the Execute stage is active and running. */
    inline void activateStage();

    /** Tells CPU that the Execute stage is inactive and idle. */
    inline void deactivateStage();

    /** Returns if the LSQ has any stores to writeback. */
    bool hasStoresToWB() { return ldstQueue.hasStoresToWB(); }

    /** Returns if the LSQ has any stores to writeback. */
    bool hasStoresToWB(ThreadID tid) { return ldstQueue.hasStoresToWB(tid); }

    void incrWb(InstSeqNum &sn)
    {
        if (++wbOutstanding == wbMax)
            ableToIssue = false;
        DPRINTF(EdgeExe, "wbOutstanding: %i\n", wbOutstanding);
        assert(wbOutstanding <= wbMax);
#ifdef DEBUG
        wbList.insert(sn);
#endif
    }

    void decrWb(InstSeqNum &sn)
    {
        if (wbOutstanding-- == wbMax)
            ableToIssue = true;
        DPRINTF(EdgeExe, "wbOutstanding: %i\n", wbOutstanding);
        assert(wbOutstanding >= 0);
#ifdef DEBUG
        assert(wbList.find(sn) != wbList.end());
        wbList.erase(sn);
#endif
    }

#ifdef DEBUG
    std::set<InstSeqNum> wbList;

    void dumpWb()
    {
        std::set<InstSeqNum>::iterator wb_it = wbList.begin();
        while (wb_it != wbList.end()) {
            cprintf("[sn:%lli]\n",
                    (*wb_it));
            wb_it++;
        }
    }
#endif

    bool canIssue() { return ableToIssue; }

    bool ableToIssue;

  private:
    /** Sends commit proper information for a squash due to a syscall
    *    requirement.
    */
    void squashDueToSyscall(EdgeBlockPtr &inst_block, ThreadID tid);

    /** Sends commit proper information for a squash due to a branch
     * mispredict.
     */
    void squashDueToBranch(EdgeBlockPtr &inst_block, ThreadID tid);

    /** Sends commit proper information for a squash due to a memory order
     * violation.
     */
    void squashDueToMemOrder(EdgeBlockPtr &inst_block, ThreadID tid);

    /** Sends commit proper information for a squash due to memory becoming
     * blocked (younger issued instructions must be retried).
     */
    void squashDueToMemBlocked(EdgeBlockPtr &inst_block, ThreadID tid);

    /** Sets Dispatch to blocked, and signals back to other stages to block. */
    void block(ThreadID tid);

    /** Unblocks Dispatch if the skid buffer is empty, and signals back to
     * other stages to unblock.
     */
    void unblock(ThreadID tid);

    /** Determines proper actions to take given Dispatch's status. */
    void dispatch(ThreadID tid);

    /** Dispatches instructions to IQ and LSQ. */
    void dispatchInsts(ThreadID tid);

    /** Executes instructions. In the case of memory operations, it informs the
     * LSQ to execute the instructions. Also handles any redirects that occur
     * due to the executed instructions.
     */
    void executeInstBlocks();

    /** Detect the completed blocks. Completion of inst blocks will be judged
     * according to the completion conditions of this block. Block completed
     * means all the insts in this block have received its operands and all but
     * the write-reg insts and store insts have been executed. Write-reg and
     * store will write back after commit stage confirm the commit condition
     * of this block. When we complete one block, we should wait the commit
     * signal from commit stage to write back write-reg and store. Moreover,
     * misprediction of one block will be detected once the block completes.
     */
    void completeInstBlocks();

    /** Returns the number of valid, non-squashed inst blocks coming from
     * map to dispatch.
     */
    unsigned validInstBlocksFromMap();

    /** Reads the stall signals. */
    void readStallSignals(ThreadID tid);

    /** Checks if any of the stall conditions are currently true. */
    bool checkStall(ThreadID tid);

    /** Processes inputs and changes state accordingly. */
    void checkSignalsAndUpdate(ThreadID tid);

    /** Removes inst blocks from map from a thread's inst block list. */
    void emptyMapInstBlocks(ThreadID tid);

    /** Sorts inst blocks coming from rename into lists separated by thread. */
    void sortInstBlocks();

    /** Get the current frame id for dispatching inst blocks into inst queue. */
    int getCurrFrameID();

    /** Decrease the frame id if an inst block is squashed. */
    void decCurrFrameID();

  public:
    /** Ticks Execute stage, causing Dispatch, the IQ, the LSQ, Execute, and
     * Writeback to run for one cycle.
     */
    void tick();

  private:
    /** Updates execution stats based on the inst blocks. */
    void updateExeInstBlockStats();

    /** Pointer to main time buffer used for backwards communication. */
    TimeBuffer<TimeStruct> *timeBuffer;

    /** Wire to write information heading to previous stages. */
    typename TimeBuffer<TimeStruct>::wire toFetch;

    /** Wire to write information heading to previous stages. */
    typename TimeBuffer<TimeStruct>::wire toMap;

    /** Wire to get commit's output from backwards time buffer. */
    typename TimeBuffer<TimeStruct>::wire fromCommit;

    /** Issue stage queue. */
    TimeBuffer<Issue2Execute> issueToExecQueue;

    /** Wire to read information from the issue stage time queue. */
    typename TimeBuffer<Issue2Execute>::wire fromIssue;

    /**
     * Execute stage time buffer.
     */
    TimeBuffer<Execute2Commit> *execute2commitQueue;

    TimeBuffer<Map2Execute> *map2executeQueue;

    /** Wire to write infromation heading to commit. */
    typename TimeBuffer<Execute2Commit>::wire toCommit;

    /** Wire to get inst blocks from map stage time buffer. */
    typename TimeBuffer<Map2Execute>::wire fromMap;

    /** Queue of all inst blocks coming from map this cycle. */
    std::queue<EdgeBlockPtr> instBlocks[Impl::MaxThreads];

    /** Hold inst block objects currently in executing. */
    std::map<BlockID, EdgeBlockPtr> instBlocksInExecuting;

    /** Current frame id for dispatching inst blocks to inst queue. */
    int currFrameID;

    /** Skid buffer between Map and Execute. */
    std::queue<EdgeBlockPtr> skidBuffer[Impl::MaxThreads];

  private:
    /** CPU pointer. */
    CPU *cpu;

    /** Records if Execute has written to the time buffer this cycle, so that the
     * CPU can deschedule itself if there is no activity.
     */
    bool wroteToTimeBuffer;

    /** Source of possible stalls. */
    struct Stalls {
        bool commit;
    };

    /** Stages that are telling Execute to stall. */
    Stalls stalls[Impl::MaxThreads];

  public:
    /** Instruction queue. */
    IQ instQueue;

    /** Load / store queue. */
    LSQ ldstQueue;

    /** Pointer to the functional unit pool. */
    FUPool *fuPool;

    /** Records if the LSQ needs to be updated on the next cycle, so that
     * Execute knows if there will be activity on the next cycle.
     */
    bool updateLSQNextCycle;

  private:
    /** Records if there is a fetch redirect on this cycle for each thread. */
    bool fetchRedirect[Impl::MaxThreads];

    /** Records if the queues have been changed (inserted or issued insts),
     * so that Execute knows to broadcast the updated amount of free entries.
     */
    bool updatedQueues;

    /** Commit to Execute delay, in ticks. */
    unsigned commitToExecuteDelay;

    /** Map to Execute delay, in ticks. */
    unsigned mapToExecuteDelay;

    /**
     * Issue to execute delay, in ticks.  What this actually represents is
     * the amount of time it takes for an instruction to wake up, be
     * scheduled, and sent to a FU for execution.
     */
    unsigned issueToExecuteDelay;

    /** Width of dispatch, in instructions. */
    unsigned dispatchWidth;

    /** Width of issue, in instructions. */
    unsigned issueWidth;

    /** Index into queue of instructions being written back. */
    unsigned wbNumInstBlock;

    /** Cycle number within the queue of instructions being written back.
     * Used in case there are too many instructions writing back at the current
     * cycle and writesbacks need to be scheduled for the future. See comments
     * in instToCommit().
     */
    unsigned wbCycle;

    /** Number of instructions in flight that will writeback. */
    int wbOutstanding;

    /** Writeback width. */
    unsigned wbWidth;

    /** Writeback width * writeback depth, where writeback depth is
     * the number of cycles of writing back instructions that can be
     * buffered. */
    unsigned wbMax;

    /** Number of active threads. */
    ThreadID numThreads;

    /** Pointer to list of active threads. */
    std::list<ThreadID> *activeThreads;

    /** Maximum size of the skid buffer. */
    unsigned skidBufferMax;

    /** Is this stage switched out. */
    bool switchedOut;

    /** Stat for total number of idle cycles. */
    Stats::Scalar executeIdleCycles;
    /** Stat for total number of squashing cycles. */
    Stats::Scalar executeSquashCycles;
    /** Stat for total number of blocking cycles. */
    Stats::Scalar executeBlockCycles;
    /** Stat for total number of unblocking cycles. */
    Stats::Scalar executeUnblockCycles;

    /** Stat for total number of instructions dispatched. */
    Stats::Scalar executeDispatchedInsts;
    /** Stat for total number of NOPs dispatched. */
    Stats::Scalar executeDispNopInsts;
    /** Stat for total number of useful insts dispatched. */
    Stats::Formula executeDispUsefulInsts;
    /** Stat for total number of inst blocks dispatched. */
    Stats::Scalar executeDispatchedInstBlocks;
    /** Stat for total number of squashed instructions dispatch skips. */
    Stats::Scalar executeDispSquashedInsts;
    /** Stat for total number of squashed inst blocks dispatch skips. */
    Stats::Scalar executeDispSquashedInstBlocks;
    /** Stat for total number of dispatched load instructions. */
    Stats::Scalar executeDispLoadInsts;
    /** Stat for total number of dispatched store instructions. */
    Stats::Scalar executeDispStoreInsts;
    /** Stat for total number of dispatched non speculative instructions. */
    Stats::Formula executeDispSpecInstBlocks;
    /** Stat for total number of dispatched non speculative inst blocks. */
    Stats::Scalar executeDispNonSpecInstBlocks;
    /** Stat for total number of dispatched non speculative insts. */
    Stats::Scalar executeDispNonSpecInsts;
    /** Stat for total number of dispatched non speculative insts. */
    Stats::Formula executeDispSpecInsts;

    /** Stat for number of times the IQ becomes full. */
    Stats::Scalar executeIQFullEvents;
    /** Stat for number of times the LSQ becomes full. */
    Stats::Scalar executeLSQFullEvents;
    /** Stat for number of times the Max in-flight inst blocks reached. */
    Stats::Scalar executeInFlightFullEvents;
    /** Stat for total number of memory ordering violation events. */
    Stats::Scalar memOrderViolationEvents;
    /** Stat for total number of load blocked events. */
    Stats::Scalar memLoadBlockedEvents;
    /** Stat for total number of mispredicted branches detected at execute. */
    Stats::Scalar branchMispredicts;

    /** Stat for total number of executed instructions. */
    Stats::Scalar executeExecutedInsts;
    /** Stat for total number of executed inst blocks. */
    Stats::Scalar executeExecutedInstBlocks;
    /** Number of executed memory references. */
    Stats::Scalar executeExecutedRefs;
    /** Stat for total number of executed load instructions. */
    Stats::Scalar executeExecLoadInsts;
    /** Number of executed store instructions. */
    Stats::Formula executeExecStoreInsts;
    /** Stat for total number of squashed instructions skipped at execute. */
    Stats::Scalar executeExecSquashedInsts;
    /** Stat for total number of squashed inst blocks skipped at execute. */
    Stats::Scalar executeExecSquashedInstBlocks;
    /** Stat for total number of executed reg-read instructions. */
    Stats::Scalar executeExecRegReads;
    /** Stat for total number of executed reg-write instructions. */
    Stats::Scalar executeExecRegWrites;
    /** Number of executed register accesses. */
    Stats::Formula executeExecRegAcc;
    /** Stat for total number of nullified instructions. */
    Stats::Formula executeExecNullifiedInsts;
    /** Stat for total number of nullified stores. */
    Stats::Scalar executeExecNullifiedStores;
    /** Stat for total number of nullified loads. */
    Stats::Scalar executeExecNullifiedLoads;
    /** Stat for total number of nullified reg-writes. */
    Stats::Scalar executeExecNullifiedWrites;
    /** Stat for total number of nullified branches. */
    Stats::Scalar executeExecNullifiedBranches;
    /** Stat for total number of nullified normal insts. */
    Stats::Scalar executeExecNullifiedNormals;
    /** Number of instructions executed per cycle. */
    Stats::Formula executeExecRate;
    /** Number of cycles have available insts. */
    Stats::Scalar executeExecAvailCycles;

    /** Number of instructions sent to commit. */
    Stats::Scalar executeInstBlocksToCommit;

    /** Distribution of in-flight blocks. */
    Stats::Distribution executeInflightInstBlocks;

    /** Distribution of in-filght insts. */
    Stats::Distribution executeInflightInsts;    
};

#endif // __CPU_EDGE_EXE_HH__
